package com.linchong.dynamicprogramming.medium;

/**
 * @author linchong
 * @version 1.0
 * @Date: 2020-11-17 22:04
 * @Description: MinCost$256-粉刷房子-https://leetcode-cn.com/problems/paint-house/
 */
public class PaintHouseI {

	/**
	 * 序列型动态规划
	 * 假如有一排房子，共 n 个，每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种，你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。
	 *
	 * 当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n x 3 的矩阵来表示的。
	 *
	 * 例如，costs[0][0] 表示第 0 号房子粉刷成红色的成本花费；costs[1][2] 表示第 1 号房子粉刷成绿色的花费，以此类推。请你计算出粉刷完所有房子最少的花费成本。
	 *
	 * 注意：
	 *
	 * 所有花费均为正整数。
	 *
	 *
	 * 示例：
	 *
	 * 输入: [[17,2,17],[16,16,5],[14,3,19]]
	 * 输出: 10
	 * 解释: 将 0 号房子粉刷成蓝色，1 号房子粉刷成绿色，2 号房子粉刷成蓝色。
	 *      最少花费: 2 + 5 + 3 = 10。
	 *
	 * 来源：力扣（LeetCode）
	 * 链接：https://leetcode-cn.com/problems/paint-house
	 *
	 *
	 *
	 *  这种序列化的动态规划问题，前n栋即0到n-1
	 *
	 *
	 * 【解析】：
	 *
	 *      （1）最优策略是花费最小的策略，
	 *      （2）最后一步中，最优策略房子N-1一定被染成了红、绿、蓝三种颜色中的一种
	 *      （3）但是，相邻的房子不能漆成同一种颜色
	 *      （4）综上：
	 *          如果房子N-1漆成了红色，则房子N-2只能漆成绿色或蓝色
	 *          如果房子N-1漆成了绿色，则房子N-2只能漆成红色或蓝色
	 *          如果房子N-1漆成了蓝色，则房子N-2只能漆成绿色或红色
	 *      记录了前n栋房子的花费(即房子N-1)，根据套路，也需要记录油漆前N-1栋房子的最小花费（即房子N-2）
	 *      但是，递推前N-1栋房子的最小花费的最优策略时，不知道房子N-2是什么颜色，所以有可能和房子N-1撞色
	 *
	 *      解决：不知道房子N-2是什么颜色，就把它记录下来。即不只是记录油漆前N-1栋房子的最小花费，而是同时记录下前N-1栋房子的颜色信息，
	 *      即记录前N-1栋房子的最小花费且房子N-2的颜色是红、蓝、绿颜色的最小花费。
	 *
	 *  序列型动态规划，前i栋房子，却只到i-1,看起来别扭，但是序列型动态规划都是如此，含义如下：我们定义房子，第0栋房子是0，第1栋房子是1，第
	 *  2栋房子是2...,前3栋房子是房子0、房子1、房子2，前3栋房子的最后一栋不是3而是2，所以前i栋房子的最后一个就是i-1,这样处理的原因是因为
	 *  在序列化型动态规划中，从f(0)开始，f(0)就是没有房子，就是前0栋房子，油漆花费就是0，不同于坐标型动态规划，坐标型，下标就是坐标，它中
	 *  的f[0]代表到第0个元素位置，第0个元素即f[0],有值
	 *  1.确定状态：
	 *          最后一步：
	 *              若房子N-1是红色，则房子N-2是蓝/绿色
	 *              若房子N-1是绿色，则房子N-2是蓝/红色
	 *              若房子N-1是蓝色，则房子N-2是红/绿色
	 *
	 *          子问题：
	 *              求油漆前N栋房子且房子N-1是红色、蓝色、绿色的最小花费->需要知道油漆前N-1栋房子并且房子N-2是红色、蓝色、绿色的最小花费
	 *
	 *          状态：f[i][0],f[i][1],f[i][2]
	 *
	 *  2.状态转移方程
	 *      设油漆前i栋房子且房子i-1是红色、蓝色、绿色的最小花费分别为：
	 *          f[i][0]、f[i][1]、f[i][2]
	 *      因而有：
	 *      f[i][0] = min{f[i-1][1]+cost[i-1][0],f[i-1][2]+cost[i-1][0]}
	 *      油漆前i栋房子且房子i-1是红色的花费  油漆前i-1栋房子花费并且房子i-2是蓝色的最小花费加上油漆房子i-1的花费 油漆前i-1栋房子花费并且房子i-2是绿色的最小花费加上油漆房子i-1的花费
	 *      f[i][1] = min{f[i-1][0]+cost[i-1][1],f[i-1][2]+cost[i-1][1]}
	 *      f[i][2] = min{f[i-1][0]+cost[i-1][2],f[i-1][1]+cost[i-1][2]}
	 *
	 *  3.初始值和边界
	 *      序列型动态规划，前多少个的初始化条件都是0，即前0个，都是空
	 *      设油漆的前i栋房子且房子i-1是红色、蓝色、绿色的最小花费分别是f[i][0]、f[i][1]、f[i][2]
	 *          初始条件：f[0][0] = f[0][1] = f[0][2] = 0
	 *          无边界
	 *  4.计算顺序
	 *      设油漆的前i栋房子且房子i-1是红色、蓝色、绿色的最小花费分别是f[i][0]、f[i][1]、f[i][2]
	 *      初始化f[0][0],f[0][1],f[0][2] ... f[N][0],f[N][1],f[N][2]
	 *
	 *      结果：min{f[N][0],f[N][1],f[N][2]},时间复杂度O(n),空间复杂度O(n)
	 *
	 */
	public int minCost(int[][] costs) {

		// 多少栋房子
		int n = costs.length;

		if(n==0){
			return 0;
		}
		// 动态方程数组，计算最小花费的同时记录颜色
		int[][] f = new int[n+1][3];
		int i,j,k,res;
		// init
		f[0][0] = f[0][1] = f[0][2] =  0;
		// 前1栋房子到前n栋房子
		for (i = 1; i <= n; i++) {
			// 前i栋房子的最后一栋房子设置为j，j is the color of house i-1
			for (j = 0;  j< 3; j++) {
				// 设置最大，寻找替换
				f[i][j] = Integer.MAX_VALUE;
				// k is the color of house i-2
				for (k = 0; k < 3; k++) {
					// 房子i-1同房子i-2撞色
					if(j==k){
						continue;
					}
					// 前i-1栋房子且最后一栋房子i-2颜色是k,房子i-1漆成颜色j
					// 0到i-2,   前i栋房子的最后一栋房子
					if(f[i-1][k]+costs[i-1][j]<f[i][j]){
						f[i][j] = f[i-1][k]+costs[i-1][j];
					}
				}
			}
		}
		res = f[n][0];
		if(f[n][1]<res){
			res = f[n][1];
		}

		if(f[n][2]<res){
			res = f[n][2];
		}
		return res;
	}
	public static void main(String[] args) {
		int[][] costs = {{17,2,17},{16,16,5},{14,3,19}};
		PaintHouseI cost = new PaintHouseI();
		cost.minCost(costs);
	}

}
